{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 案例\n",
    "\n",
    "\n",
    "应用场景：\n",
    "\n",
    "本文使用决策树对**web站点的用户在线浏览行为**及**最终购买行为（选择的服务类型或者用户类型）进行预测。**\n",
    "\n",
    "每个用于的在线浏览行为信息包括：每个用户的来源网站、用户的ip位置、是否阅读FAQ、浏览网页数目。\n",
    "\n",
    "目标分类为用户类型：\n",
    "\n",
    ">游客、基本用户、高级用户\n",
    "\n",
    "在建立决策树时，我们先要懂得一个概念，叫属性的分类重要性，就是某个属性的出现，对目标结果能带来多大的信息。\n",
    "\n",
    "属性的重要程度是根据样本数据集使用该属性进行划分子集后，集合的纯度增加了多少来决定。\n",
    "\n",
    "我们以用户在线浏览信息为例，如果阅读过FAQ的用户全部都是高级用户，没有阅读过FAQ的都是基本用户，则是否阅读过FAQ这个属性就非常重要。\n",
    "\n",
    "因为通过FAQ属性划分子集后，产生的两个子集，非常“纯”。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "决策树的建立过程是先找出最重要的分类属性，再找出第二重要的分类属性。以此建立树的层次。\n",
    "\n",
    "| 算法        | 支持模型   |  树结构  |   特征选择 | 连续值处理|  缺失值处理 |  剪枝 | \n",
    "| --------   | -----  | ----  |----  |----  |----  |----  |\n",
    "|ID3 |分类 |多叉树 |信息增益| 不支持  |不支持 | 不支持 |\n",
    "|C4.5 |分类 |多叉树| 信息增益比 |支持 | 支持 | 支持 |\n",
    "|CART |分类，回归| 二叉树| 基尼系数，均方差| 支持 | 支持 | 支持 |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 构建数据集\n",
    "\n",
    "\n",
    "读者可以自己去获取自家公司的用户行为记录，这里给出一个简单的数据集\n",
    "\n",
    "下面的数据为每个用户的来源网站、位置、是否阅读FAQ、浏览网页数目、以及用户类型（None为游客，Basic为基本用户，Premium为高级用户）。\n",
    "\n",
    "最后一列属性为用户类型，就是我们想要预测的分类结果"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "my_data=[['slashdot','USA','yes',18,'None'],\n",
    "         ['google','France','yes',23,'Premium'],\n",
    "         ['digg','USA','yes',24,'Basic'],\n",
    "         ['kiwitobes','France','yes',23,'Basic'],\n",
    "         ['google','UK','no',21,'Premium'],\n",
    "         ['(direct)','New Zealand','no',12,'None'],\n",
    "         ['(direct)','UK','no',21,'Basic'],\n",
    "         ['google','USA','no',24,'Premium'],\n",
    "         ['slashdot','France','yes',19,'None'],\n",
    "         ['digg','USA','no',18,'None'],\n",
    "         ['google','UK','no',18,'None'],\n",
    "         ['kiwitobes','UK','no',19,'None'],\n",
    "         ['digg','New Zealand','yes',12,'Basic'],\n",
    "         ['slashdot','UK','no',21,'None'],\n",
    "         ['google','UK','yes',18,'Basic'],\n",
    "         ['kiwitobes','France','yes',19,'Basic']]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 决策树前的准备工作\n",
    "\n",
    "\n",
    "有了样本数据集，我们就可以用来构建决策树了。\n",
    "\n",
    "在构建决策树的过程中：\n",
    "\n",
    "①首先我们要对决策树上的点创建类\n",
    "\n",
    "②然后要能够根据属性划分成多个子数据集\n",
    "\n",
    "③还要能计算划分子数据集后的信息增益，用信息增益来判断这个属性的重要性\n",
    "\n",
    "④然后选择最重要的属性建第一层树。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**1、为决策树上的点创建类**\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 建立决策树上的节点类\n",
    "class decisionnode:\n",
    "    def __init__(self,col=-1,value=None,results=None,tb=None,fb=None):\n",
    "        self.col=col                #待检测条件所属的列索引。即当前是对第几列数据进行分类\n",
    "        self.value=value            #为使结果为true，当前列必须匹配的值\n",
    "        self.results=results        #如果当前节点时叶节点，表示该节点的结果值，如果不是叶节点，为None\n",
    "        self.tb=tb                  #判断条件为true后的子节点\n",
    "        self.fb=fb                  #判断调节为false后的子节点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2、数据集划分功能**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这里我们完成根据属性划分数据集的功能。一般对于字符串型的数据，我们将数据集分成等于和不等于两个子集。\n",
    "\n",
    "对数值型属性，我们分成大于和小于两个子集。\n",
    "\n",
    "需要注意的是，在样本数据集中，每一行为一个对象，每一列为一种属性。样本数据集以矩阵的形式存在。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 根据某一属性对数据集合进行拆分，能够处理数值型数据或名词性数据。其实决策树只能处理离散型数据，对于连续性数据也是划分为范围区间块\n",
    "# rows样本数据集，column要匹配的属性列索引，value指定列上的数据要匹配的值\n",
    "def divideset(rows,column_index,column_value):\n",
    "    # 定义一个函数，令其告诉我们数据行属于第一组（返回值为true）还是第二组（返回值false）\n",
    "    split_function=None\n",
    "    if isinstance(column_value,int) or isinstance(column_value,float):\n",
    "        split_function=lambda row:row[column_index]>=column_value   #按大于、小于区分\n",
    "    else:\n",
    "        split_function=lambda row:row[column_index]==column_value   #按等于、不等于区分\n",
    "\n",
    "    # 将数据集拆分成两个子集，并返回\n",
    "    set1=[row for row in rows if split_function(row)]\n",
    "    set2=[row for row in rows if not split_function(row)]\n",
    "    return (set1,set2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 信息增益的计算"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "完成了拆分子集，就可以计算拆分后的信息增益了。\n",
    "\n",
    "在计算信息增益时，我们不适用纯度，而使用凌乱度，意义相同。凌乱度越大越不好。\n",
    "\n",
    "原样本集划分成多个子集后，每个子集的凌乱度我们可以由基尼不纯度的大小或熵的大小来代替。\n",
    "\n",
    "那一个原数据集和多个子集之间如何比较凌乱度呢。这除了和每个子集的凌乱度有关外，还与子集的大小有关。\n",
    "\n",
    "因为如果其中一个子集样本数非常少，即使凌乱度非常低也不能代表什么。\n",
    "\n",
    "划分后的多个子集的总体凌乱度我们设定为**m=p1*m1+p2*m2+p3*m3。**其中p1、p2、p3为每个子集所占的比例，m1、m2、m3为每个子集的凌乱度。\n",
    "\n",
    "用没有划分子集前的原样本数据集的凌乱度减去多个子集的总体凌乱度，就是信息增益。信息增益越大，证明该属性对分类的重要程度越大。\n",
    "\n",
    "这里每个子集使用基尼不纯度或熵来代表凌乱度。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**1、基尼不纯度**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    ">子集计算基尼不纯度，即随机放置的数据项出现于错误分类中的概率。以此来评判属性对分类的重要程度。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$Gini(p)=∑p_k (1−p_k )=1−∑ p^2_k  $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "换句话说，就是统计集合中所有分类的概率两两积的和。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "比如下面的rows是通过一个属性划分的一个子集。我们肯定希望这个子集中尽可能都是同一种分类。\n",
    "\n",
    "这样这个子集的纯度才能够高。如何看纯度够不够高呢。\n",
    "\n",
    "比如这个集合有包含了3个分类，分类1的比例是0.1，分类2的比例是0.1，分类3的比例是0.8。这3个比例的两两积的和为0.1*0.1+0.1*0.8+0.1*0.8 = 0.17\n",
    "\n",
    "而如果这三个分类中，分类1的比例为0.3，分类2的比例为0.3，分类3的比例为0.4，则这3个比例的两两积的和为0.3*0.3+0.3*0.4+0.3*0.4=0.33，是不是比上面的大，表明纯度小。\n",
    "\n",
    "为什么会存在这种大小关系呢？自己百度吧。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "#rows样本数据集\n",
    "def giniimpurity(rows):\n",
    "    total=len(rows)\n",
    "    counts=uniquecounts(rows)\n",
    "    imp=0\n",
    "    for k1 in counts:\n",
    "        p1=float(counts[k1])/total\n",
    "        for k2 in counts:\n",
    "            if k1==k2: continue\n",
    "            p2=float(counts[k2])/total\n",
    "            imp+=p1*p2\n",
    "    return imp\n",
    "\n",
    "# 统计集合rows中每种分类的样本数目。（样本数据每一行数据的最后一列记录了分类结果）。rows样本数据\n",
    "def uniquecounts(rows):\n",
    "    results={}\n",
    "    for row in rows:\n",
    "        # 目标结果在样本数据最后一列\n",
    "        r=row[len(row)-1]\n",
    "        if r not in results: results[r]=0\n",
    "        results[r]+=1\n",
    "    return results"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2、熵**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    ">熵，即遍历所有可能的结果之后得到的p(x)log(p(x))之和。也可以以此评判属性对分类的重要程度。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "#rows样本数据集\n",
    "def entropy(rows):\n",
    "    from math import log\n",
    "    log2=lambda x:log(x)/log(2)\n",
    "    results=uniquecounts(rows)\n",
    "    # 此处开始计算熵的值\n",
    "    ent=0.0\n",
    "    for r in results.keys():\n",
    "        p=float(results[r])/len(rows)\n",
    "        ent=ent-p*log2(p)\n",
    "    return ent\n",
    "\n",
    "# 对各种可能的目标结果（选择的服务类型）进行计数（样本数据每一行数据的最后一列记录了目标结果）。rows样本数据\n",
    "def uniquecounts(rows):\n",
    "    results={}\n",
    "    for row in rows:\n",
    "        # 目标结果在样本数据最后一列\n",
    "        r=row[len(row)-1]\n",
    "        if r not in results: results[r]=0\n",
    "        results[r]+=1\n",
    "    return results"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 构建决策树 ##"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "当能判断哪个属性对分类更重要我们就可以构建决策树了，先选出最重要的属性，作为根节点，再将数据集划分成两个子集，并分别在子集中选出其次重要的属性，做为左右子树的根节点，并以此递推下去。\n",
    "\n",
    "通过每一次的属性查询，我们就知道了该找那个属性作为节点，以及该如果进行左右子树的划分。\n",
    "\n",
    "buildtree函数输入为样本数据集，输出为决策树。\n",
    "\n",
    "> 所谓的输出为决策树，就是输出的为根节点。根节点就表示决策树。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 构建决策树.scoref为信息增益的计算函数\n",
    "def buildtree(rows,scoref=entropy):\n",
    "    if len(rows)==0: return decisionnode()\n",
    "    current_score=scoref(rows)\n",
    "\n",
    "    # 定义一些变量以记录最佳拆分条件\n",
    "    best_gain=0.0\n",
    "    best_criteria=None\n",
    "    best_sets=None\n",
    "\n",
    "    column_count=len(rows[0])-1\n",
    "    for col in range(0,column_count):    #遍历每一列（除最后一列，因为最后一列是目标结果）\n",
    "        # 在当前列中生成一个由不同值构成的序列\n",
    "        column_values={}\n",
    "        for row in rows:\n",
    "            column_values[row[col]]=1\n",
    "        # 接下来根据这一列中的每个值，尝试对数据集进行拆分\n",
    "        for value in column_values.keys():\n",
    "            (set1,set2)=divideset(rows,col,value)\n",
    "\n",
    "            # 计算信息增益\n",
    "            p=float(len(set1))/len(rows)\n",
    "            gain=current_score-p*scoref(set1)-(1-p)*scoref(set2)\n",
    "            if gain>best_gain and len(set1)>0 and len(set2)>0:   #找到信息增益最大的分类属性\n",
    "                best_gain=gain\n",
    "                best_criteria=(col,value)\n",
    "                best_sets=(set1,set2)\n",
    "    # 创建子分支\n",
    "    if best_gain>0:\n",
    "        trueBranch=buildtree(best_sets[0])   #创建分支\n",
    "        falseBranch=buildtree(best_sets[1])  #创建分支\n",
    "        return decisionnode(col=best_criteria[0],value=best_criteria[1],tb=trueBranch,fb=falseBranch)  #返回决策树节点\n",
    "    else:\n",
    "        return decisionnode(results=uniquecounts(rows))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 绘制决策树"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Looking in indexes: https://mirrors.tencent.com/pypi/simple/, https://mirrors.tencent.com/repository/pypi/tencent_pypi/simple\n",
      "Collecting Pillow\n",
      "  Downloading https://mirrors.tencent.com/pypi/packages/20/cb/261342854f01ff18281e97ec8e6a7ce3beaf8e1091d1cebd52776049358d/Pillow-9.2.0-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (3.1 MB)\n",
      "     |████████████████████████████████| 3.1 MB 7.3 MB/s            \n",
      "\u001b[?25hInstalling collected packages: Pillow\n",
      "Successfully installed Pillow-9.2.0\n",
      "\u001b[33mWARNING: Running pip as the 'root' user can result in broken permissions and conflicting behaviour with the system package manager. It is recommended to use a virtual environment instead: https://pip.pypa.io/warnings/venv\u001b[0m\n",
      "\u001b[33mWARNING: You are using pip version 21.3.1; however, version 22.2.2 is available.\n",
      "You should consider upgrading via the '/usr/bin/python -m pip install --upgrade pip' command.\u001b[0m\n"
     ]
    }
   ],
   "source": [
    "! pip install Pillow"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "from PIL import Image, ImageDraw\n",
    "\n",
    "# 获取树的显示宽度\n",
    "def getwidth(tree):\n",
    "    if tree.tb==None and tree.fb==None: return 1\n",
    "    return getwidth(tree.tb)+getwidth(tree.fb)\n",
    "\n",
    "# 获取树的显示深度（高度）\n",
    "def getdepth(tree):\n",
    "    if tree.tb==None and tree.fb==None: return 0\n",
    "    return max(getdepth(tree.tb),getdepth(tree.fb))+1\n",
    "\n",
    "# 绘制树形图\n",
    "def drawtree(tree,jpeg='tree.jpg'):\n",
    "    w=getwidth(tree)*100\n",
    "    h=getdepth(tree)*100+120\n",
    "\n",
    "    img=Image.new('RGB',(w,h),(255,255,255))\n",
    "    draw=ImageDraw.Draw(img)\n",
    "\n",
    "    drawnode(draw,tree,w/2,20)  #根节点坐标\n",
    "    img.save(jpeg,'JPEG')\n",
    "\n",
    "# 迭代画树的节点\n",
    "def drawnode(draw,tree,x,y):\n",
    "    if tree.results==None:\n",
    "        # 得到每个分支的宽度\n",
    "        w1=getwidth(tree.fb)*100\n",
    "        w2=getwidth(tree.tb)*100\n",
    "\n",
    "        # 确定此节点所要占据的总空间\n",
    "        left=x-(w1+w2)/2\n",
    "        right=x+(w1+w2)/2\n",
    "\n",
    "        # 绘制判断条件字符串\n",
    "        draw.text((x-20,y-10),str(tree.col)+':'+str(tree.value),(0,0,0))\n",
    "\n",
    "        # 绘制到分支的连线\n",
    "        draw.line((x,y,left+w1/2,y+100),fill=(255,0,0))\n",
    "        draw.line((x,y,right-w2/2,y+100),fill=(255,0,0))\n",
    "\n",
    "        # 绘制分支的节点\n",
    "        drawnode(draw,tree.fb,left+w1/2,y+100)\n",
    "        drawnode(draw,tree.tb,right-w2/2,y+100)\n",
    "    else:\n",
    "        txt=' \\n'.join(['%s:%d'%v for v in tree.results.items()])\n",
    "        draw.text((x-20,y),txt,(0,0,0))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![这里写图片描述](https://img-blog.csdnimg.cn/img_convert/6961712b9621ec20a98a212dc2c1b57b.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 使用决策树对新的待测数据进行分类"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 对新的观测数据进行分类。observation为观测数据。tree为建立好的决策树\n",
    "def classify(observation,tree):\n",
    "    if tree.results!=None:\n",
    "        return tree.results\n",
    "    else:\n",
    "        v=observation[tree.col]\n",
    "        branch=None\n",
    "        if isinstance(v,int) or isinstance(v,float):\n",
    "            if v>=tree.value: branch=tree.tb\n",
    "            else: branch=tree.fb\n",
    "        else:\n",
    "            if v==tree.value: branch=tree.tb\n",
    "            else: branch=tree.fb\n",
    "        return classify(observation,branch)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 剪枝操作"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在决策树创建时，由于数据中的噪声和离群点，许多分支反应的是训练数据中的异常，或者构建决策树时选取的阈值较小，造成构造的决策树特别复杂。\n",
    "\n",
    "这些都导致决策树对训练数据的分类效果很好，但是对未知数据的分类效果不理想，也就是过拟合现象。\n",
    "\n",
    "我们通过剪支方法处理这种过拟合数据问题。通常，这种方法使用统计量剪掉最不可靠的分支，一颗未剪枝的树和剪支的树对比如图。剪支后树更小，更简单，判断更快更好。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如图中，比如属性A1的值为no时正常情况都应该属于分类B，但是由于噪声原因，存在了几个属性A1的值为no的，却属于分类A的对象。所以在决策树时就会多出一条分支。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![这里写图片描述](https://img-blog.csdnimg.cn/img_convert/d045c83b20bb71fa6ffbf373b69baded.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "剪支分为先剪支和后剪支。后剪支更常用，就是先完整的构建一个树，再通过删除节点的分支并用树叶替换它而剪掉给定节点上的子树。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "剪支的过程就是对具有相同父节点的一组节点进行检查，判断如果将其合并，熵的增加量是否会小于某个指定的阈值。\n",
    "\n",
    "如果确实如此，则这些叶节点会被合并成一个单一的节点，合并后的新节点包含了所有可能的结果值。\n",
    "\n",
    "这种做法有助于避免过度拟合的情况，也使得根据决策树做出的预测结果，不至于比从数据集中得到的实际结论还要特殊。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "CART树的剪枝算法中使用的是用交叉验证来检验剪枝后的预测能力，选择泛化预测能力最好的剪枝后的数作为最终的CART树。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 决策树剪枝。(因为有些属性的分类产生的熵值的差太小，没有区分的必要)，mingain为门限。\n",
    "# 为了避免遇到大小台阶的问题（子树分支的属性比较重要），所以采取先建树，再剪支的方式\n",
    "def prune(tree,mingain):\n",
    "    # 如果分支不是叶节点，则对其进行剪枝操作\n",
    "    if tree.tb.results==None:\n",
    "        prune(tree.tb,mingain)\n",
    "    if tree.fb.results==None:\n",
    "        prune(tree.fb,mingain)\n",
    "\n",
    "    # 如果两个自分支都是叶节点，则判断他们是否需要合并\n",
    "    if tree.tb.results!=None and tree.fb.results!=None:\n",
    "        # 构建合并后的数据集\n",
    "        tb,fb=[],[]\n",
    "        for v,c in tree.tb.results.items():\n",
    "            tb+=[[v]]*c\n",
    "        for v,c in tree.fb.results.items():\n",
    "            fb+=[[v]]*c\n",
    "\n",
    "        # 检查熵的减少情况\n",
    "        delta=entropy(tb+fb)-(entropy(tb)+entropy(fb)/2)\n",
    "\n",
    "        if delta<mingain:\n",
    "            # 合并分支\n",
    "            tree.tb,tree.fb=None,None\n",
    "            tree.results=uniquecounts(tb+fb)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 对于缺失数据的情况\n",
    "\n",
    "对包含缺失数据的新的待测数据进行分类。会在逐层分类到缺失属性层时，不知道该往哪个方向继续判断。\n",
    "\n",
    "这时可以支同时查询每个分支，这样就有多个最终分类结果。最后计算多个分类的结果的加权结果。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mdclassify(observation,tree):\n",
    "    if tree.results!=None:\n",
    "        return tree.results\n",
    "    else:\n",
    "        v=observation[tree.col]\n",
    "        if v==None:\n",
    "            tr,fr=mdclassify(observation,tree.tb),mdclassify(observation,tree.fb) #分别使用左右子树进行分类预测\n",
    "            # 求统计结果\n",
    "            tcount=sum(tr.values())\n",
    "            fcount=sum(fr.values())\n",
    "            tw=float(tcount)/(tcount+fcount)\n",
    "            fw=float(fcount)/(tcount+fcount)\n",
    "            result={}\n",
    "            for k,v in tr.items(): result[k]=v*tw\n",
    "            for k,v in fr.items(): result[k]=v*fw\n",
    "            return result\n",
    "        else:\n",
    "            if isinstance(v,int) or isinstance(v,float):\n",
    "                if v>=tree.value: branch=tree.tb\n",
    "                else: branch=tree.fb\n",
    "            else:\n",
    "                if v==tree.value: branch=tree.tb\n",
    "                else: branch=tree.fb\n",
    "            return mdclassify(observation,branch)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 对于数值型输出结果\n",
    "\n",
    "\n",
    "如果输出结果不是分类而是数字，可以使用方差作为评价函数来取代熵或基尼不纯度"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "#计算数据集的统计方差\n",
    "def variance(rows):\n",
    "    if len(rows)==0: return 0\n",
    "    data=[float(row[len(row)-1]) for row in rows]\n",
    "    mean=sum(data)/len(data)\n",
    "    variance=sum([(d-mean)**2 for d in data])/len(data)\n",
    "    return variance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 测试代码"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<__main__.decisionnode object at 0x7f1f5a3dda00>\n",
      "{'Premium': 2.25, 'Basic': 0.25}\n"
     ]
    }
   ],
   "source": [
    "if __name__=='__main__':  #只有在执行当前模块时才会运行此函数\n",
    "    tree = buildtree(my_data)   #创建决策树\n",
    "    print(tree)\n",
    "    drawtree(tree,jpeg='treeview.jpg')  #画树形图\n",
    "    prune(tree,0.1)   #剪支\n",
    "    result = mdclassify(['google',None,'yes',None],tree)   #使用决策树进行预测，新数据包含缺失数据\n",
    "    print(result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![title](treeview.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "决策树的内容到这里就讲完了。下面我们来总结一下。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**决策树优点**\n",
    "\n",
    "1、决策树易于理解和实现，人们在在学习过程中不需要使用者了解很多的背景知识，这同时是它的能够直接体现数据的特点，只要通过解释后都有能力去理解决策树所表达的意义。\n",
    "\n",
    "2、对于决策树，数据的准备往往是简单或者是不必要的，而且能够同时处理数据型和常规型属性，在相对短的时间内能够对大型数据源做出可行且效果良好的结果。\n",
    "\n",
    "3、易于通过静态测试来对模型进行评测，可以测定模型可信度；如果给定一个观察的模型，那么根据所产生的决策树很容易推出相应的逻辑表达式。\n",
    "\n",
    "**决策树缺点**\n",
    "\n",
    "1)对连续性的字段比较难预测。\n",
    "\n",
    "2)对有时间顺序的数据，需要很多预处理的工作。\n",
    "\n",
    "3)当类别太多时，错误可能就会增加的比较快。\n",
    "\n",
    "4)一般的算法分类的时候，只是根据一个字段来分类。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Regression Decision Tree：回归树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "回归树总体流程类似于分类树，区别在于，回归树的每一个节点都会得一个预测值。\n",
    "\n",
    "以年龄为例，该预测值等于属于这个节点的所有人年龄的平均值。\n",
    "\n",
    "分枝时穷举每一个feature的每个阈值找最好的分割点，但衡量最好的标准不再是最大熵，而是最小化平方误差。\n",
    "\n",
    "也就是被预测出错的人数越多，错的越离谱，平方误差就越大，通过最小化平方误差能够找到最可靠的分枝依据。\n",
    "\n",
    "分枝直到每个叶子节点上人的年龄都唯一或者达到预设的终止条件(如叶子个数上限)，若最终叶子节点上人的年龄不唯一，则以该节点上所有人的平均年龄做为该叶子节点的预测年龄。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![这里写图片描述](https://img-blog.csdnimg.cn/img_convert/29786c02147b1dc0b561affde5c89b0f.png)\n",
    "\n",
    "![这里写图片描述](https://img-blog.csdnimg.cn/img_convert/747b69ff088cd1fd7f91957ff938ea50.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 思考：选哪些特征属性参与决策树建模、哪些属性排在决策树的顶部，哪些排在底部，对属性的值该进行什么样的判断、样本属性的值缺失怎么办、如果输出不是分类而是数值能用么、对决策没有用或没有多大帮助的属性怎么办、什么时候使用决策树？"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
